package basis.netease.hard;

import java.util.Scanner;
import java.util.Stack;

/**
 * 7-15 最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * 输入格式:
 * 包含 '(' 和 ')' 的字符串
 * 输出格式:
 * 有效括号子串的长度
 * 输入样例1:
 * 在这里给出一组输入。例如：
 * (()
 * 输出样例1:
 * 在这里给出相应的输出。例如：
 * 2
 * 解释：最长有效括号子串是 "()"
 * 输入样例2:
 * 在这里给出一组输入。例如：
 * )()(()))
 * 输出样例2:
 * 在这里给出相应的输出。例如：
 * 6
 * 解释：最长有效括号子串是 "()(())"
 * 输入样例3:
 * 在这里给出一组输入。例如：
 * 输出样例3:
 * 在这里给出相应的输出。例如：
 * 0
 * 提示：
 * 0 <= s.length <= 3 * 104
 * s[i] 为 '(' 或 ')'
 */
public class Main_12 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(cal(sc.nextLine()));
    }

    // 方法1：动态规划
    public static int cal(String s) {
        // dp[i]表示以第i个字符结尾的最长有效括号子串的长度，只记录字符是')'时的有效长度。
        int[] dp = new int[s.length()];
        int maxLength = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                // 如果第i-1个字符是'('，可以直接和第i个字符组成一个有效括号，所以就是第i-2个字符有效括号长度加2
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    // 如果第i-1个字符也是')'，并且再往前dp[i-1]+1个字符是'('，则dp[i]为前一个字符的有效长度加2，再加上更前面的有效长度(往前dp[i-1]+2个字符)。
                    dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }

    // 方法2：栈
    public static int cal2(String s) {
        int maxLength = 0;
        // stack栈只存'('的索引值
        Stack<Integer> stack = new Stack<>();
        // 标记最近一次可能为有效括号的初始位置
        int start = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    // 栈为空，说明不可能再与之前的括号形成有效括号，更新标记位
                    start = i;
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        // 匹配')'后栈为空，说明标记位到i位置全部都是有效括号
                        maxLength = Math.max(maxLength, i - start);
                    } else {
                        // 匹配')'后栈不为空，直接取栈顶
                        maxLength = Math.max(maxLength, i - stack.peek());
                    }
                }
            }
        }
        return maxLength;
    }


}
